package com.hardy.data_structure;

/**
 * Author: Hardy
 * Date:   2020/7/5
 * Description:
 * - 归并
 * - nlogn, n
 **/
public class SortMerge {

    public static void main(String[] args) {

        int[] a = {1, 2, 6, 3, 8, 0, 3};

        sort(a);

        System.out.println(a);
    }

    private static void sort(int[] a) {
        sortSplit(a, 0, a.length - 1);
    }

    // [1, 2, 3, 4, 5, 6]
    private static void sortSplit(int[] a, int i, int j) {
        if (i >= j) return;

        // 只有两个元素
        if (j - i == 1) {
            if (a[i] > a[j]) {
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
            return;
        }

        int mid = (j + i) / 2;

        sortSplit(a, i, mid - 1);
        sortSplit(a, mid, j);

        merge(a, i, j, mid);
    }

    private static void merge(int[] a, int start, int end, int mid) {
        int[] temp = new int[end - start + 1];
        int idx = 0;

        int i = start;
        int k = mid;

        while (true) {
            if (i > mid - 1 && k > end) return;

            // 前为空
            if (i > mid - 1) {
                while (k <= end) temp[idx++] = a[k++];
                break;
            }

            // 后为空
            if (k > end) {
                while (i <= mid - 1) temp[idx++] = a[i++];
                break;
            }

            if (a[i] <= a[k]) {
                temp[idx++] = a[i++];
            } else {
                temp[idx++] = a[k++];
            }
        }

        // 更新
        for (int x = 0; x < temp.length; x++) {
            a[start++] = temp[x];
        }
    }
}

